package com.xk._02算法篇._08dynamicProgramming;

/**
 * @description: 最长公共子序列：求两个序列的最长公共子序列长度
 * @author: xu
 * @date: 2022/10/19 9:04
 */
public class LCS {
    public static void main(String[] args) {
        int[] nums1 = new int[]{ 1, 3, 5, 9, 10 };
        int[] nums2 = new int[]{ 1, 4, 9, 10 };

        int res = new LCS().lcs(nums1, nums2);
        System.out.println(res);
    }

    // 动态规划 -- 优化 一维数组
    // 时间：O(n*m) 空间：O(k) k = min(nums1.length, nums2.length)
    public int lcs(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int[] rowNums = nums1, colNums = nums2;
        if (nums1.length < nums2.length) {
            rowNums = nums2;
            colNums = nums1;
        }
        int[] dp = new int[colNums.length + 1];
        for (int i = 1; i <= rowNums.length; i++) {
            int cur = 0;
            for (int j = 1; j <= colNums.length; j++) {
                int leftTop = cur;
                cur = dp[j];
                if (rowNums[i - 1] == colNums[j - 1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j-1], dp[j]);
                }
            }
        }
        return dp[colNums.length];
    }

    // 动态规划 -- 优化 一维数组
    // 时间：O(n*m) 空间：O(n)
    public int lcs4(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int len1 = nums1.length, len2 = nums2.length;
        int[] dp = new int[len2 + 1];
        for (int i = 1; i <= len1; i++) {
            int cur = 0;
            for (int j = 1; j <= len2; j++) {
                int leftTop = cur;
                cur = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j-1], dp[j]);
                }
            }
        }
        return dp[len2];
    }

    // 动态规划 -- 优化 滚动数组
    // 时间：O(n*m) 空间：O(m)
    public int lcs3(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int len1 = nums1.length, len2 = nums2.length;
        // dp[i][j] 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
        // i = [0,nums1.length]  j = [0,nums2.length]
        int[][] dp = new int[2][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            int row = i & 1;
            int prevRow = (i - 1) & 1;
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[row][j] = dp[prevRow][j-1] + 1;
                } else {
                    dp[row][j] = Math.max(dp[row][j-1], dp[prevRow][j]);
                }
            }
        }
        return dp[len1 & 1][len2];
    }

    // 动态规划
    // 时间：O(n*m) 空间：O(n*m)
    public int lcs2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int len1 = nums1.length, len2 = nums2.length;
        // dp[i][j] 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
        // i = [0,nums1.length]  j = [0,nums2.length]
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[len1][len2];
    }

    // 递推
    // 时间：O(2^n) 空间：O(k) k == Math.min(nums1.length, nums2.length)
    public int lcs1(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        return lcs1(nums1, nums1.length, nums2, nums2.length);
    }
    /**
     * 求 num1 前 i 个元素和 nums2 前 j 个元素的最长公共子序列长度
     */
    private int lcs1(int[] nums1, int i, int[] nums2, int j) {
        if (i == 0 || j == 0) return 0;
        if (nums1[i - 1] == nums2[j - 1]) {
            return lcs1(nums1, i - 1, nums2, j - 1) + 1;
        }
        return Math.max(lcs1(nums1,i - 1, nums2, j), lcs1(nums1, i, nums2, j - 1));
    }



    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.isEmpty()) return 0;
        if (text2 == null || text2.isEmpty()) return 0;

        char[] rowChars = text1.toCharArray(), colChars = text2.toCharArray();
        if (text1.length() < text2.length()) {
            char[] tmp = rowChars;
            rowChars = colChars;
            colChars = tmp;
        }
        int[] dp = new int[colChars.length + 1];
        for (int i = 1; i <= rowChars.length; i++) {
            int cur = 0;
            for (int j = 1; j <= colChars.length; j++) {
                int leftTop = cur;
                cur = dp[j];
                if (rowChars[i-1] == colChars[j-1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
            }
        }
        return dp[colChars.length];
    }


    public int longestCommonSubsequence1(String text1, String text2) {
        if (text1 == null || text1.isEmpty()) return 0;
        if (text2 == null || text2.isEmpty()) return 0;
        return longestCommonSubsequence1(text1.toCharArray(), text2.toCharArray());
    }
    public int longestCommonSubsequence1(char[] text1, char[] text2) {
        int len1 = text1.length, len2 = text2.length;
        int[] dp = new int[len2 + 1];
        for (int i = 1; i <= len1; i++) {
            int cur = 0;
            for (int j = 1; j <= len2; j++) {
                int leftTop = cur;
                cur = dp[j];
                if (text1[i-1] == text2[j-1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
            }
        }
        return dp[len2];
    }
}
